package com.zhouchb.test;


import com.sun.xml.internal.ws.api.message.HeaderList;

import java.security.interfaces.ECKey;
import java.util.ArrayList;
import java.util.List;

/**
 * @Author Zhouchb
 * @Create 2021-11-2021/11/3 :20:54
 * @Description
 */

class test {
    public static void main(String[] args) {

        tree<Integer, Integer> tree = new tree<>();
        tree.put(5,5);
        tree.put(2,2);
        tree.put(7,7);
        tree.put(1,1);
        tree.put(4,4);
        tree.put(6,6);
        tree.put(8,8);
        tree.put(3,3);
        System.out.println(tree.N);
        for (Object o : tree.preOrder()) {
            System.out.print(o);
            System.out.print("-");
        }
        System.out.println();
        for (Object o : tree.midOrder()) {
            System.out.print(o);
            System.out.print("=");
        }


//        tree.del(2);
//        System.out.println(tree.N);
    }
}

public class tree<Key extends Comparable<Key>, Value> {

    private Node root;
    public Integer N = 0;

    class Node {
        private Key key;
        private Value value;
        private Node leftNode;
        private Node rightNode;

        public Node(Key key, Value value, Node left, Node right) {
            this.key = key;
            this.value = value;
            this.leftNode = left;
            this.rightNode = right;
        }
    }

    public void put(Key key, Value value) {
        root = put(root, key, value);
    }

    public Node put(Node x, Key key, Value value) {
        if (x == null) {
            x = new Node(key, value, null, null);
            N++;
            return x;
        }
        int cmp = key.compareTo(x.key);
        if (cmp > 0) {
            x.rightNode = put(x.rightNode, key, value);
        } else if (cmp < 0) {
            x.leftNode = put(x.leftNode, key, value);
        } else {
            x.value = value;
        }
        return x;
    }

    public void del(Key key) {
        root = del(root, key);
    }

    public Node del(Node x, Key key) {
        if (x==null){
            return null;
        }
        int cmp = key.compareTo(x.key);
        if (cmp>0){
            x.rightNode = del(x.rightNode,key);
        }else if (cmp<0){
            x.leftNode = del(x.leftNode,key);
        }else {
            N--;
            if (x.rightNode == null){
                return x.leftNode;
            }
            if (x.leftNode == null){
                return x.rightNode;
            }
            Node minNode = x.rightNode;
            while (minNode.leftNode != null){
                if (minNode.leftNode.leftNode == null){
                    minNode = minNode.leftNode;
                    minNode.leftNode = null;
                }else {
                    minNode = minNode.leftNode;
                }

            }

            minNode.leftNode = x.leftNode;
            minNode.rightNode = x.rightNode;
            x = minNode;
        }
        return x;
    }
    //前序遍历
   public List preOrder(){
       List list = new ArrayList();
       preOrder(root,list);
       return list;
   }
   public void preOrder(Node x,List list){
        if (x==null){
            return;
        }
        list.add(x.key);
        preOrder(x.leftNode,list);
        preOrder(x.rightNode,list);
   }
   //中序遍历
    public List midOrder(){
        List list = new ArrayList();
        midOrder(root,list);
        return list;
    }
    public void midOrder(Node x,List list){
        if (x==null){
            return;
        }
        midOrder(x.leftNode,list);
        list.add(x.key);
        midOrder(x.rightNode,list);

    }
}
